package com.example.leetcode.DFS;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 *46
 *
 * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 *
 * candidates 中的每个数字在每个组合中只能使用一次。
 *
 * 说明：
 *
 * 所有数字（包括目标数）都是正整数。
 * 解集不能包含重复的组合。 
 * 示例 1:
 *
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 * 所求解集为:
 * [
 *   [1, 7],
 *   [1, 2, 5],
 *   [2, 6],
 *   [1, 1, 6]
 * ]
 * 示例 2:
 *
 * 输入: candidates = [2,5,2,1,2], target = 5,
 * 所求解集为:
 * [
 *   [1,2,2],
 *   [5]
 * ]
 *
 *
 * @ClassName Soluction_11_40
 * @Description TODO
 * @Author liuzhihui
 * @Date 14/6/2021 下午 9:12
 * @Version 1.0
 **/
public class Soluction_11_40 {
    public static void main(String[] args) {
        int[] candidates = new int[]{10,1,2,7,6,1,5};
        List<List<Integer>> lists = combinationSum2(candidates, 8);
    }
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        // 排序,以便剪枝 1 1 2 5 6 7 10
        Arrays.sort(candidates);
        dfs(candidates, target, temp, result,0);
        result = result.stream().distinct().collect(Collectors.toList());
        return result;
    }
    // 回溯+剪纸
    private static void dfs(int[] candidates, int target, List<Integer> temp, List<List<Integer>> result,int begin) {
        //递归出口：找到一种组合
        if (target == 0) {
            result.add(new ArrayList<>(temp));
            return;
        }
        //遍历数组candidates
        for (int i = begin; i < candidates.length; i++) {
            // 排除：元素直接大于taget的情况
            if (target < candidates[i]) {
                break;
            }
            // 剪枝
            // 比如说有个数组 [1, 1, 7] target = 8
            // 经过上面的去重，我们得到的最终答案是 [[1, 7], [1, 7]] 这显然不是我们想要的
            // 究其原因在于，对两个1都进行了选择。针对这种情况，解决办法如下：
            // 在同一轮循环中，跳过和已访问过元素数值相同的元素们。
            // i要与i-1比较，所以 i>begin
            if (i > begin && candidates[i] == candidates[i - 1]) {
                continue;
            }
            temp.add(candidates[i]);
            // 下次循环从位置 i + 1 开始，因为每个元素在每个组合中只能使用一次。
            // 如果集合选取了 a + b + c = target， 那么我们就不要再选择 a + c + b = target了
            // 这个比较好实现，只要保证下一次递归的起点在本次访问下标的下一个位置即可，也就是说如果本次执行了
            // 递归到下一层调用时，选择的起点就是i+1 这样就可以实现对 顺序排列的a b c 只可顺序的选取。
            dfs(candidates, target - candidates[i],temp,result,i + 1);
            // 回溯
            temp.remove(temp.size() - 1);
        }
    }




}
